/**
 * 0206
 *
 * @Author : Ruoyu Wang
 * @DateTime : 2024/8/13 20:56
 */

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 递归反转链表
//class Solution {
//private:
//    ListNode *reverse(ListNode *s, ListNode *p) {
//        if (p == nullptr) return s;
//        ListNode *tmp = p->next;
//        p->next = s;
//        return reverse(p, tmp);
//    }
//
//public:
//    ListNode *reverseList(ListNode *head) {
//        return reverse(nullptr, head);
//    }
//};

// 循环反转链表
class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode *cur = new ListNode(-1, nullptr);
        ListNode *p;
        while (head != nullptr) {
            p = head->next;
            head->next = cur->next;
            cur->next = head;
            head = p;
        }
        return cur->next;
    }
};

int main() {

    return 0;
}